from typing import Optional

# (112. 路径总和)[https://leetcode.cn/problems/path-sum/?envType=problem-list-v2&envId=depth-first-search]
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(node, cur_sum) -> bool:
            if not node:
                return False

            cur_sum += node.val

            # 到叶子节点，判断路径和
            if not node.left and not node.right:
                return cur_sum == targetSum

            return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)

        return False if dfs(root, 0) == 0 else True


    # (113. 路径总和 II)[https://leetcode.cn/problems/path-sum-ii/submissions/623874365/?envType=problem-list-v2&envId=depth-first-search]
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        result = []
        path = []

        def dfs(node, cur_sum):
            if not node:
                return

            cur_sum += node.val
            path.append(node.val)

            # 叶子节点，且路径和=targetSum
            if not node.left and not node.right and cur_sum == targetSum:
                result.append(path[:])

            dfs(node.left, cur_sum)
            dfs(node.right, cur_sum)

            path.pop()

        dfs(root, 0)

        return result

    # (114. 二叉树展开为链表)[https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=problem-list-v2&envId=depth-first-search]
    def flatten(self, root: Optional[TreeNode]) -> None:
        # 辅助函数：递归的将二叉树展开
        def flatten_tree(node):
            if not node:
                return None

            # 如果是叶子节点，返回自己
            left = flatten_tree(node.left)  # 展开左子树
            right = flatten_tree(node.right)  # 展开右子树

            # 如果有左子树
            if left:
                # 根节点接上左子树（此时的right相当于链表的next）
                node.right = left
                # 将左子树的最右节点与右子树连接
                while left.right:
                    left = left.right
                left.right = right

            # 断开左子树
            node.left = None

            # 返回当前节点（已展开的部分）
            return node

    # [235. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/?envType=problem-list-v2&envId=depth-first-search)
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while root:
            # 如果两节点都大于根节点，则公共祖先在右侧
            if p.val > root.val and q.val > root.val:
                root = root.right
            # 如果两节点都小于根节点，则公共祖先在左侧
            elif p.val < root.val and q.val < root.val:
                root = root.left
            else:
                return root

    # [99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/description/?envType=problem-list-v2&envId=depth-first-search)
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        first = second = prev = None

        # 中序遍历: 二叉搜索树严格递增
        def inOrder(node):
            nonlocal first, second, prev
            if not node:
                return
            inOrder(node.left)

            # 判断规则
            if prev and prev.val > node.val:
                if not first:  # 第一次出现递减
                    first = prev
                second = node

            prev = node
            inOrder(node.right)

        inOrder(root)
        if first and second:
            first.val, second.val = second.val, first.val

    # [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/description/?envType=problem-list-v2&envId=depth-first-search)

    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            # 如果当前节点为空，直接返回0
            if not node:
                return 0

            # 计算当前节点的左子树的和
            # 如果当前节点的左子树是叶子节点，直接加上左子树的值
            if node.left and not node.left.left and not node.left.right:
                return node.left.val + dfs(node.right)

            # 继续递归访问左右子树
            return dfs(node.left) + dfs(node.right)

        # 从根节点开始DFS遍历
        return dfs(root)